package com.mypaper.schedule;

import com.mypaper.elem.LinkedListNode;
import com.mypaper.elem.PairElement;
import com.mypaper.elem.ScheduleElement;
import com.mypaper.elem.ScheduleNode;
import com.mypaper.elem.TaskNode;
import com.mypaper.list.IdleList;
import com.mypaper.list.ListPriority;
import com.mypaper.list.OrderLinkedList;
import com.mypaper.list.ScheduleResults;


public class HLDSchedule extends ScheduleAlgorithm{
	public short[][] MIIP;
	float[][] EST;
	float[][] EFT;
	float[][] DEST;
	float[][] DEFT;
	float[][] DAT;
	float[][] readyTime;
	boolean[][] isScheduled;
	PairElement[] searchItem;
	PairElement[] beFoundItem;
	PairElement[] beFoundDup;
	boolean found, foundD, found2;
	private ScheduleResults[] origResultsPerProc;
	
	public HLDSchedule(short vertexNum, short procNum){
		scheduleResults=new ScheduleResults();
		reliedDup=new short[vertexNum];//每个任务依赖的duplication任务编号
		MIIP=new short[vertexNum][procNum];//每个任务在处理器上的MIIP
		AST=new float[vertexNum];//每个任务在遍历所有处理器后计算出的实际开始执行时间
		AFT=new float[vertexNum];//每个任务在遍历所有处理器后计算出的实际结束执行时间
		idleTimeList=new IdleList[procNum];//每个处理器一个空闲时间块列
		for(int i=0; i<procNum; i++){
			idleTimeList[i]=new IdleList();
			idleTimeList[i].insertNode(new PairElement(0,Float.MAX_VALUE));
		}
		EST=new float[vertexNum][procNum];//每个任务在遍历每个处理器时计算出的最早开始执行时间
		EFT=new float[vertexNum][procNum];//每个任务在遍历每个处理器时计算出的最早结束执行时间
		DEST=new float[vertexNum][procNum];//每个任务在遍历每个处理器时假设duplicate MIIP计算出的最早开始执行时间
		DEFT=new float[vertexNum][procNum];//每个任务在遍历每个处理器时假设duplicate MIIP计算出的最早结束执行时间
		MEST=new float[vertexNum][procNum];//每个任务在遍历每个处理器时假设duplicate时MIIP计算出的最早开始执行时间
		MEFT=new float[vertexNum][procNum];//每个任务在遍历每个处理器时假设duplicate时MIIP计算出的最早结束执行时间
		DAT=new float[vertexNum][procNum];
		readyTime=new float[vertexNum][procNum];
		isScheduled=new boolean[vertexNum][procNum];
		searchItem=new PairElement[procNum];
		beFoundItem=new PairElement[procNum];
		beFoundDup=new PairElement[procNum];
		assiProc2Task=new short[vertexNum];
		found=false;
		foundD=false;
		found2=false;
		
		origResultsPerProc=new ScheduleResults[procNum];//the original schedule
		for(int i=0;i<procNum;i++){
			origResultsPerProc[i]=new ScheduleResults();			
		}
		ScheduleNode sNode=scheduleResults.first;
		while(sNode!=null){
			origResultsPerProc[sNode.info.processorID].insertNode(sNode.info);//将调度结果分解到各个处理器单独的调度结果，方便以后查找
			sNode=sNode.next;
		}
	}
	
	public void updatePerProc(int procNum){
		for(int i=0;i<procNum;i++){
			origResultsPerProc[i]=new ScheduleResults();			
		}
		ScheduleNode sNode=scheduleResults.first;
		while(sNode!=null){
			origResultsPerProc[sNode.info.processorID].insertNode(sNode.info);//将调度结果分解到各个处理器单独的调度结果，方便以后查找
			sNode=sNode.next;
		}
	}
	
	public void HLD_Algorithm(short vertexNum, short procNum, ListPriority prior, 
			float[][] vertexWeight, float[][] edgeWeight){
		int i,j;			
		for(i=0; i<procNum; i++){
			searchItem[i]=new PairElement();
			beFoundItem[i]=new PairElement();
			beFoundDup[i]=new PairElement();
		}
		
		for(i=0;i<vertexNum;i++){
			reliedDup[i]=-1;
			assiProc2Task[i]=-1;
		}
		
		isScheduled=new boolean[vertexNum][procNum];
		
		for(i=0; i<vertexNum; i++){
			AST[i]=Float.MAX_VALUE;
			AFT[i]=Float.MAX_VALUE;
			for(j=0; j<procNum; j++){		
				EST[i][j]=Float.MAX_VALUE;
				EFT[i][j]=Float.MAX_VALUE;
				DEFT[i][j]=Float.MAX_VALUE;
				DEST[i][j]=Float.MAX_VALUE;
				isScheduled[i][j]=false;
				MIIP[i][j]=-1;
				DAT[i][j]=Float.MAX_VALUE;
				readyTime[i][j]=0;
			}
		}
		
		float AFT_back=Float.MAX_VALUE;
		
		OrderLinkedList[] idleTimeListBack=new OrderLinkedList[procNum];
		OrderLinkedList[] idleTimeListBackDup=new OrderLinkedList[procNum];
		for(i=0; i<procNum; i++){
			idleTimeListBack[i]=new OrderLinkedList();
			idleTimeListBackDup[i]=new OrderLinkedList();
			idleTimeListBack[i].insertNode(new PairElement(0,Float.MAX_VALUE));
			idleTimeListBackDup[i].insertNode(new PairElement(0,Float.MAX_VALUE));
		}
		
		TaskNode currentTask=prior.first;
		ScheduleElement perTask=new ScheduleElement();//为每个任务的调度结果暂时存储分配空间
		
		short assiProc=-1;
		while(currentTask!=null){
			int currTaskIndex=currentTask.info.index;
			//System.out.println("currTask: "+currTaskIndex);
			for(short k=0; k<procNum; k++){
				updatePerProc(procNum);
				for(short l=0; l<vertexNum; l++){//求所有父节点在当前处理器上的到达时间及当前任务的MIIP
					if(edgeWeight[l][currTaskIndex]!=0){
						//if(assiProc2Task[l]==k)//对于每个父节点，求到达处理器的时间
						updatePerProc(procNum);
						if(origResultsPerProc[k].findTask(l)!=null)
							DAT[l][k]=Math.min(AFT[l]+edgeWeight[l][currTaskIndex],origResultsPerProc[k].findTask(l).endTime);
						else{
							DAT[l][k]=AFT[l]+edgeWeight[l][currTaskIndex];
						}
						if(readyTime[currTaskIndex][k]<DAT[l][k]){//找MIIP父节点及其到达时间
							readyTime[currTaskIndex][k]=DAT[l][k];
							MIIP[currTaskIndex][k]=l;
						}	
					}	
				}
				if(MIIP[currTaskIndex][k]!=-1){
					readyTime[MIIP[currTaskIndex][k]][k]=0;
					for(short l=0; l<vertexNum; l++){//求所有父节点在当前处理器上的到达时间及当前任务的MIIP
						if(edgeWeight[l][MIIP[currTaskIndex][k]]!=0){
							updatePerProc(procNum);
							if(origResultsPerProc[k].findTask(l)!=null)
								DAT[l][k]=Math.min(AFT[l]+edgeWeight[l][MIIP[currTaskIndex][k]],origResultsPerProc[k].findTask(l).endTime);
							else{
								DAT[l][k]=AFT[l]+edgeWeight[l][MIIP[currTaskIndex][k]];
							}
							if(readyTime[MIIP[currTaskIndex][k]][k]<DAT[l][k]){//找MIIP父节点及其到达时间
								readyTime[MIIP[currTaskIndex][k]][k]=DAT[l][k];
							}	
						}	
					}
				}
				//找插入的空闲块并处理
				idleTimeListBack[k].copyList(idleTimeList[k]);
				found=false;
				float startT=readyTime[currTaskIndex][k];
				float endT=readyTime[currTaskIndex][k]+vertexWeight[currTaskIndex][k];
				LinkedListNode currentIdle=idleTimeList[k].first;//处理器K上第一个空闲块
				while(currentIdle!=null&&!found){
					searchItem[k].setNum(startT, endT);
					//要为searchItem找合适的空闲时间
					beFoundItem[k]=(PairElement)idleTimeListBack[k].search(searchItem[k]);//beFoundItem为找到的空闲时间段
					if(beFoundItem[k]!=null)
						found=true;
					currentIdle=currentIdle.next;
				}
				if(found==true){//更新空闲时间链表
					EST[currTaskIndex][k]=Math.max(searchItem[k].start, beFoundItem[k].start);
					EFT[currTaskIndex][k]=EST[currTaskIndex][k]+vertexWeight[currTaskIndex][k];	
					idleTimeListBack[k].deleteNode(beFoundItem[k]);
					if(searchItem[k].start>beFoundItem[k].start){
						idleTimeListBack[k].insertNode(new PairElement(beFoundItem[k].start,EST[currTaskIndex][k]));
						idleTimeListBack[k].insertNode(new PairElement(EFT[currTaskIndex][k],beFoundItem[k].end));
					}else{
						idleTimeListBack[k].insertNode(new PairElement(EFT[currTaskIndex][k],beFoundItem[k].end));
					}
				}
				
				//下面判断duplication情况下是否减小EFT
				int miip=MIIP[currTaskIndex][k];//记录当前任务的MIIP;
				float RT;
				idleTimeListBackDup[k].copyList(idleTimeList[k]);
				currentIdle=idleTimeListBackDup[k].first;//处理器K上第一个空闲块
				if(miip!=-1&&isScheduled[miip][k]==false){//MIIP存在并且MIIP未在k上执行
					RT=readyTime[miip][k];//MIIP的所需数据到达k的时间
					foundD=false;
					while(currentIdle!=null&&!foundD){
						searchItem[k].setNum(RT, RT+vertexWeight[miip][k]);
						beFoundDup[k]=(PairElement)idleTimeListBackDup[k].search(searchItem[k]);
						if(beFoundDup[k]!=null)
							foundD=true;
						currentIdle=currentIdle.next;
					}
				
					if(foundD==true){//找到可供复制的空闲时间，计算MIIP的结束时间及currentTask的开始结束时间
						MEST[miip][k]=Math.max(RT, beFoundDup[k].start);
						MEFT[miip][k]=MEST[miip][k]+vertexWeight[miip][k];	
						idleTimeListBackDup[k].deleteNode(beFoundDup[k]);
						if(searchItem[k].start>beFoundDup[k].start){
							idleTimeListBackDup[k].insertNode(new PairElement(beFoundDup[k].start,MEST[miip][k]));
							idleTimeListBackDup[k].insertNode(new PairElement(MEFT[miip][k],beFoundDup[k].end));
						}else{
							idleTimeListBackDup[k].insertNode(new PairElement(MEFT[miip][k],beFoundDup[k].end));
						}
						
						float readyTimeBack=MEFT[miip][k];//MIIP可能变了

						if(readyTimeBack<EST[currTaskIndex][k]){//如果duplication task结束提前
							
							for(int l=0; l<vertexNum; l++){//求所有父节点在当前处理器上的到达时间及当前任务的MIIP
								if(edgeWeight[l][currTaskIndex]!=0){	
									updatePerProc(procNum);
									if(origResultsPerProc[k].findTask(l)!=null)
										DAT[l][k]=Math.min(AFT[l]+edgeWeight[l][currTaskIndex],origResultsPerProc[k].findTask(l).endTime);
									else{
										DAT[l][k]=AFT[l]+edgeWeight[l][currTaskIndex];
									}
									
									if(l!=miip && readyTimeBack<DAT[l][k]){//找MIIP父节点及其到达时间
										readyTimeBack=DAT[l][k];
									}
								}	
							}
							
							startT=readyTimeBack;
							endT=readyTimeBack+vertexWeight[currTaskIndex][k];
							
							found2=false;
							currentIdle=idleTimeListBackDup[k].first;
							while(currentIdle!=null&&!found2){
								searchItem[k].setNum(startT, endT);
								//要为searchItem找合适的空闲时间						
								//beFoundItem[k].makeCopy((PairElement)idleTimeListBackDup[k].search(searchItem[k]));//beFoundItem为找到的空闲时间段
								beFoundItem[k]=(PairElement)idleTimeListBackDup[k].search(searchItem[k]);//beFoundItem为找到的空闲时间段
								if(beFoundItem[k]!=null)
									found2=true;
								currentIdle=currentIdle.next;
							}
							if(found2==true){//更新空闲时间链表
								DEST[currTaskIndex][k]=Math.max(searchItem[k].start, beFoundItem[k].start);
								DEFT[currTaskIndex][k]=DEST[currTaskIndex][k]+vertexWeight[currTaskIndex][k];	
								idleTimeListBackDup[k].deleteNode(beFoundItem[k]);
								if(searchItem[k].start>beFoundItem[k].start){
									idleTimeListBackDup[k].insertNode(new PairElement(beFoundItem[k].start,DEST[currTaskIndex][k]));
									idleTimeListBackDup[k].insertNode(new PairElement(DEFT[currTaskIndex][k],beFoundItem[k].end));
								}else{
									idleTimeListBackDup[k].insertNode(new PairElement(DEFT[currTaskIndex][k],beFoundItem[k].end));
								}
							}
						}
					}
				}
				if(AFT_back>Math.min(EFT[currTaskIndex][k], DEFT[currTaskIndex][k])){
					AFT_back=Math.min(EFT[currTaskIndex][k], DEFT[currTaskIndex][k]);
					assiProc=k;
				}
			}
			AFT[currTaskIndex]=AFT_back;
			AST[currTaskIndex]=AFT[currTaskIndex]-vertexWeight[currTaskIndex][assiProc];
			assiProc2Task[currTaskIndex]=assiProc;
			isScheduled[currTaskIndex][assiProc]=true;
			AFT_back=Float.MAX_VALUE;
			
			if(EFT[currTaskIndex][assiProc]>DEFT[currTaskIndex][assiProc]){	
				isScheduled[MIIP[currTaskIndex][assiProc2Task[currTaskIndex]]][assiProc]=true;
				perTask.setNum(MIIP[currTaskIndex][assiProc2Task[currTaskIndex]],
						assiProc2Task[currTaskIndex],
						MEST[MIIP[currTaskIndex][assiProc2Task[currTaskIndex]]][assiProc2Task[currTaskIndex]],
						MEFT[MIIP[currTaskIndex][assiProc2Task[currTaskIndex]]][assiProc2Task[currTaskIndex]]);
				scheduleResults.insertNode(perTask);
				reliedDup[currTaskIndex]=MIIP[currTaskIndex][assiProc2Task[currTaskIndex]];
				idleTimeList[assiProc2Task[currTaskIndex]].copyList(idleTimeListBackDup[assiProc2Task[currTaskIndex]]);
				//scheduleResults.print();
				//System.out.println();
			}
			else{
				idleTimeList[assiProc2Task[currTaskIndex]].copyList(idleTimeListBack[assiProc2Task[currTaskIndex]]);
			}					
			perTask.setNum(currTaskIndex,assiProc2Task[currTaskIndex],AST[currTaskIndex],AFT[currTaskIndex]);
			scheduleResults.insertNode(perTask);
			//scheduleResults.print();
			//System.out.println();
			
			currentTask=currentTask.next;
			}	
		//scheduleResults.print();
		//System.out.println();
		//dag.prior.print();
		}
	
	public float energyCal(int procNum){
		float enerSum=0;
        float timeSum=0;	
        float totalTime=0;
        float power=(float)0.925, idlePower=(float)0.260;
        boolean[] flag=new boolean[procNum];
        float[] procTermTime=new float[procNum];
        ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			ScheduleElement perTask=currentTask.info;
			if(flag[perTask.processorID]!=true)
				flag[perTask.processorID]=true;
			if(perTask.endTime>procTermTime[perTask.processorID])
				procTermTime[perTask.processorID]=perTask.endTime;
			timeSum+=(perTask.endTime-perTask.startTime);
			currentTask=currentTask.next;
		}
		
		for(int i=0; i<procNum; i++){
			System.out.println("End time of processor "+i+" is "+procTermTime[i]);
			totalTime+=procTermTime[i];
		}
		System.out.println("idletime： "+(totalTime-timeSum));
		System.out.println("busytime： "+timeSum);
		enerSum=timeSum*power+(totalTime-timeSum)*idlePower;
		return enerSum;
	}
	
	
	public float makespan(){
		float curr=0;
		ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			if(curr<currentTask.info.endTime)
				curr=currentTask.info.endTime;
			currentTask=currentTask.next;
		}
		return curr;
	}
	
	public int duplNums(int taskNum){
		return scheduleResults.count-taskNum;
	}
	
	public float timeCal(int procNum){
        float timeSum=0;	
        float totalTime=0;
        boolean[] flag=new boolean[procNum];
        float[] procTermTime=new float[procNum];
        ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			ScheduleElement perTask=currentTask.info;
			if(flag[perTask.processorID]!=true)
				flag[perTask.processorID]=true;
			if(perTask.endTime>procTermTime[perTask.processorID])
				procTermTime[perTask.processorID]=perTask.endTime;
			timeSum+=(perTask.endTime-perTask.startTime);
			currentTask=currentTask.next;
		}
		
		for(int i=0; i<procNum; i++){
			//System.out.println("End time of processor "+i+" is "+procTermTime[i]);
			totalTime+=procTermTime[i];
		}
		//System.out.println("idletime： "+(totalTime-timeSum));
		System.out.println("busytime： "+timeSum);
		System.out.println();
		return timeSum;
	}
}
